import java.util.HashMap;
import java.util.function.BiFunction;

class TwoSum {
    public static void main(String[] args) {
        test(TwoSum::bruteForceSolution);
        test(TwoSum::mapSolution);
    }

    // 测试用例
    public static void test(BiFunction<int[], Integer, int[]> f) {
        System.out.println();
        int[] r = f.apply(new int[] { 2, 7, 11, 15 }, 9);
        System.out.println(r[0] + " " + r[1]);  // 0 1

        r = f.apply(new int[] { 3, 2, 4 }, 6);
        System.out.println(r[0] + " " + r[1]);  // 1 2

        r = f.apply(new int[]{3, 3}, 6);
        System.out.println(r[0] + " " + r[1]);  // 0 1
    }

    // 暴力算法 O(n^2)
    public static int[] bruteForceSolution(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    // 使用哈希表 O(n*logn)
    public static int[] mapSolution(int[] nums, int target) {
        var map = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            int firstNum = target - nums[i];

            // 和他配对的数字出现在了前面
            if (map.containsKey(firstNum)) {
                return new int[]{map.get(firstNum), i};
            }

            // 数字 映射到 其在数组中的索引
            map.put(nums[i], i);
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}